Various systems have been adopted to carry digitally-encoded signals for communication applications, such as telephone, video, and data services. These systems are often connection-oriented packet mode transmission systems, such as Asynchronous Transfer Mode (AT) systems, fame relay systems, X.25 systems, or other transmission Systems. Connection-oriented systems (e.g., ATM systems) are employed in private and public communication systems or networks to transfer packetized signals (e.g., data cells or protocol data units) across communication lines, such as telephone lines, cables, optical fibers, air waves, satellite links, or other communication media.
ATM networks transfer fixed size data cells or units via virtual connections or channels. Data cells can represent voice, sound, video, graphics, data, or combinations thereof for use in computing or communication applications. A connection could occupy a full physical link or may be part of a single physical link carrying a number of virtual connections.
Traffic management is critical to the successful operation of cell-based transmission in ATM-based networks. Cell-based transmission systems are subject to congestion caused by unpredictable statistical fluctuations of traffic flows and fault conditions within the network. Congestion of such systems refers to the state of network devices, such as switches, in which the device is not able to meet the negotiated network performance objectives for the already established connections and/or for the new connection requests. In the absence of effective traffic management, traffic loads from users can exceed the capacity of the network, resulting in an overall degradation of network performance and the loss of data. Traffic management is required in cell based networks as well as in packet based network. Traffic management maintains QoS (Quality of Service) of traffic across network elements such as switches. Where congestion occurs, traffic management allows selected traffic to be discarded in order to keep to an agreed traffic contract and to maintain traffic efficiency.
In an ATM-based network for example, the traffic control strategy is based on determining whether an ATM connection can be accommodated by the network and negotiating the performance parameters that will be supported. Traffic parameters describe the traffic characteristics of an ATM connection. For example, traffic parameters may describe peak cell rate (PCR), cell delay variation (CDV), cell delay variation tolerance (CDVT), burst tolerance (BT), sustainable cell rate (SCR),. When a user requests a new ATM connection the user must specify the traffic parameters for that connection. The user specifies the traffic parameters by selecting a QOS from the QOS classes provided by the network. A connection is accepted by the network if the necessary resources are available to support the traffic level while maintaining the agreed upon QOS for existing connections. A similar process is performed for other network types that offer quality of service guarantees.
Where a connection is established, the network and the user enter into a “contract”. The contract refers to the negotiated characteristics of an ATM connection and includes the conformance definition that is used to unambiguously specify the behaviour level the connection's cells should reach if they are to be defined as conforming cells. The agreed QOS should be provided by the network for as long as the user complies with the traffic contract, that is cells are defined as conforming.
A contract may be for one of a number of predefined service classes. Service classes include constant bit rate (CBR) and variable bit rate (VBR).
The constant bit rate service class (CBR) is intended to support real-time applications that require a fixed quantity of bandwidth during the existence of the connection and low cell delay variation. A quality of service is negotiated to provide the CBR service, where the QoS parameters include the peak cell rate (PCR) and the cell delay variation tolerance (CDVT). Conventional ATM traffic management schemes for CBR classes guarantee that the user-contracted QoS is maintained in order to support, for example, real-time applications, such as circuit emulation and voice/video applications, which require tightly constrained delay variations. A CBR class often requires that a connection is able to send a specific number of cells or bits per second A CBR class connection must have a set end-to-end bandwidth.
The variable bit rate (VBR) service class is intended to support applications where the resulting network traffic can be characterized as hang frequent data bursts. The VBR class QoS parameters include peak cell rate (PCR), a sustainable cell rate (SCR), cell delay variation tolerance (CDVT) and maximum burst tolerance (BT). Although the VBR class has somewhat more flexible timing requirements than the CBR class, the VBR class must still meet timing requirements.
ATM switches frequently employ FIFO (First In-First Out) output buffers to implement queues of cells waiting to be processed. The processing may include multiplexing the cells onto a shared link, for example. The outputs from these buffers are essentially time multiplexed composites of the input flows that are loaded into them. Of course, these output flows are time delayed relative to the input flows because of the inherent latency of the buffers. Moreover, the cell delay variation (CDV) of one or more of these output flows may be increased if scheduling conflicts occur among the data transport limits of the different flows because these conflicts cause so-called “transmit collisions”.
It will be appreciated that increased CDV is especially troublesome for traffic, such as CBR traffic, which often has a relatively tight CDV tolerance. Thus, if each hop between a source and a destination includes a simple FIFO output queue of the foregoing type, it may be necessary to limit the number of hops this CDV sensitive traffic is permitted to make in order to ensure compliance within its specified tolerance.
In order to space out bursty traffic and ensure a data source satisfies contracted connection parameters with the data it transmits, a process called shaping is performed on the output of many network devices. A shaper in a network functions to regulate traffic in a bursty network by using queues to absorb incoming bursts and then transmit the traffic in a regulated manner.
ITU-T Recommendation I.371 addresses the possibility of reshaping traffic at a network element for the purpose of bringing the traffic into conformance with a traffic descriptor in the following terms:                “Traffic shaping is a mechanism that alters the traffic characteristics of a stream of cells on a VCC or a VPC to achieve a desired modification of those traffic characteristics, in order to achieve better network efficiency whilst meeting the QoS objectives or to ensure conformance at a subsequent interface. Traffic shaping must maintain cell sequence integrity on an ATM connection. Shaping modifies traffic characteristics of a cell flow with the consequence of increasing the mean cell transfer delay.”        
Traffic shaping may be used for, for example, peak cell rate reduction, burst length limitation, and reduction of CDV by suitably spacing cells in time and queue service schemes.
Shaping for CBR classes is often implemented using a single leaky bucket algorithm whilst a dual leaky bucket algorithm is used for VBR classes.
The leaky bucket algorithm operates on the basis that traffic cells are queued in a buffer and scheduled in a periodic manner. A number of variables dependent on the traffic class of a connection are used to calculate the regular time slots in which the connection's cells can be transmitted. Unlike traffic multiplexing algorithms and other schedulers, shapers will insert delays between cells if this is necessary to space cells to satisfy contractual requirements.
In order to implement efficient shapers, the leaky bucket algorithms are implemented in logic embedded into, for example, application specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs). High-speed network devices must select a cell for transmission every few microseconds and this requires the logic to operate at exceptional high speeds. Obviously this speed requirement severely restricts the complexity of the algorithm and its implementation. Due to the required simplistic implementation only small sized variables can be used in the calculation. Reducing the size of the variables reduces the accuracy of the numbers they can store. This typically limits the variables used in the algorithms to integers or numbers with few decimal placed. Where reduced accuracy variables are used, a corresponding drop in the accuracy of the calculation can be seen. This results in traffic that is not evenly spaced or which does not meet, contractual requirements even though it has been shaped. There is therefore a trade-off between the accuracy of variables and their corresponding effect on the accuracy of the algorithm and the speed of the shaper.
Accordingly, that there is a need for more accurate traffic shaping methods and systems suitable for use in high speed ATM switches and other network devices.